﻿// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

// Based on corefx's EnumerableHelpers

using System.Diagnostics;

namespace System.Collections.Generic
{
	/// <summary>Internal helper functions for working with enumerables.</summary>
	internal static class EnumerableHelpers
	{
		/// <summary>Converts an enumerable to an array.</summary>
		/// <param name="source">The enumerable to convert.</param>
		/// <returns>The resulting array.</returns>
		internal static T[] ToArray<T>( IEnumerable<T> source )
		{
			Debug.Assert( source != null );

			var collection = source as ICollection<T>;
			if ( collection != null )
			{
				int count = collection.Count;
				if ( count == 0 )
				{
					return new T[ 0 ];
				}

				var result = new T[count];
				collection.CopyTo( result, arrayIndex: 0 );
				return result;
			}

			var builder = new List<T>();
			builder.AddRange( source );
			return builder.ToArray();
		}

		/// <summary>Converts an enumerable to an array using the same logic as List{T}.</summary>
		/// <param name="source">The enumerable to convert.</param>
		/// <param name="length">The number of items stored in the resulting array, 0-indexed.</param>
		/// <returns>
		/// The resulting array.  The length of the array may be greater than <paramref name="length"/>,
		/// which is the actual number of elements in the array.
		/// </returns>
		internal static T[] ToArray<T>( IEnumerable<T> source, out int length )
		{
			ICollection<T> ic = source as ICollection<T>;
			if ( ic != null )
			{
				int count = ic.Count;
				if ( count != 0 )
				{
					// Allocate an array of the desired size, then copy the elements into it. Note that this has the same
					// issue regarding concurrency as other existing collections like List<T>. If the collection size
					// concurrently changes between the array allocation and the CopyTo, we could end up either getting an
					// exception from overrunning the array (if the size went up) or we could end up not filling as many
					// items as 'count' suggests (if the size went down).  This is only an issue for concurrent collections
					// that implement ICollection<T>, which as of .NET 4.6 is just ConcurrentDictionary<TKey, TValue>.
					T[] arr = new T[count];
					ic.CopyTo( arr, 0 );
					length = count;
					return arr;
				}
			}
			else
			{
				using ( var en = source.GetEnumerator() )
				{
					if ( en.MoveNext() )
					{
						const int DefaultCapacity = 4;
						T[] arr = new T[DefaultCapacity];
						arr[ 0 ] = en.Current;
						int count = 1;

						while ( en.MoveNext() )
						{
							if ( count == arr.Length )
							{
								// MaxArrayLength is defined in Array.MaxArrayLength and in gchelpers in CoreCLR.
								// It represents the maximum number of elements that can be in an array where
								// the size of the element is greater than one byte; a separate, slightly larger constant,
								// is used when the size of the element is one.
								const int MaxArrayLength = 0x7FEFFFFF;

								// This is the same growth logic as in List<T>:
								// If the array is currently empty, we make it a default size.  Otherwise, we attempt to
								// double the size of the array.  Doubling will overflow once the size of the array reaches
								// 2^30, since doubling to 2^31 is 1 larger than Int32.MaxValue.  In that case, we instead
								// constrain the length to be MaxArrayLength (this overflow check works because of the
								// cast to uint).  Because a slightly larger constant is used when T is one byte in size, we
								// could then end up in a situation where arr.Length is MaxArrayLength or slightly larger, such
								// that we constrain newLength to be MaxArrayLength but the needed number of elements is actually
								// larger than that.  For that case, we then ensure that the newLength is large enough to hold
								// the desired capacity.  This does mean that in the very rare case where we've grown to such a
								// large size, each new element added after MaxArrayLength will end up doing a resize.
								int newLength = count << 1;
								if ( ( uint )newLength > MaxArrayLength )
								{
									newLength = MaxArrayLength <= count ? count + 1 : MaxArrayLength;
								}

								Array.Resize( ref arr, newLength );
							}

							arr[ count++ ] = en.Current;
						}

						length = count;
						return arr;
					}
				}
			}

			length = 0;
			return new T[ 0 ];
		}
	}
}